package com.googlecode.kipler.container.graph.isomorphism;

import java.util.Comparator;

import com.googlecode.kipler.container.graph.RelationalModel;
import com.googlecode.kipler.container.graph.RelationalNode;
import com.googlecode.kipler.container.graph.RelationalValue;

public class GraphIsomorphism<V extends RelationalValue<V, K>, R, K> {
	private Comparator<RelationalNode<V, R, K>> nodeComparator;

	public GraphIsomorphism(Comparator<RelationalNode<V, R, K>> nodeComparator) {
		this.nodeComparator = nodeComparator;
	}

	public boolean isSubgraphIsomorphic(RelationalModel<V, R, K> g1,
			RelationalModel<V, R, K> g2) {
		VF2State<V, R, K> s = new VF2State<V, R, K>(g1, g2, nodeComparator);
		return isSubgraphIsomorphic(s, Pair.initial());
	}

	private boolean isSubgraphIsomorphic(VF2State<V, R, K> s, Pair p) {
		if (s.isGoal()) {
			return true;
		}
		boolean found = false;
		while (!found && (p = s.nextPair(p)) != null) {
			if (s.isFeasiblePair(p)) {
				VF2State<V, R, K> newS = s.copy();
				newS.addPair(p);
				found = isSubgraphIsomorphic(newS, p);
			}
		}
		return found;
	}
}
